package hh.leecode.binary;


/**
 * 二分查找一个有序数组
 */
public class 二分查找 {


    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7};

        int i = binarySearch(arr, 7);

        if (i == -1) System.out.println("没找到");
        else System.out.println(arr[i]);

    }


    // 0 1 2 3 4 5 6 7
    //         y
    public static int binarySearch(int[] arr, int target) {

        int midIdx = arr.length / 2;
        int left = 0;
        int right = arr.length - 1;

        while (true) {
            if (arr[midIdx] == target) {
                return midIdx;
            }
            if (right - left == 0) return -1;

            if (target > arr[midIdx]) {
                left = midIdx + 1;
            }
            if (target < arr[midIdx]) {
                right = midIdx - 1;
            }
            midIdx = (left + right) / 2;
        }


    }


}
